package org.threads.parallelsort;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import org.utils.Utils;

import java.util.*;

/**
 * Implements a parallel merge sort algorithm.
 */
public class ParallelMergeSort {

    private static final Logger LOGGER = LoggerFactory.getLogger(ParallelMergeSort.class);

    /**
     * @param a array to sort
     * @param threadCount available threads count for sorting
     */
    public static void parallelMergeSort(int[] a, int threadCount) {

        if (a.length >= 2) {

            int[] left = Arrays.copyOfRange(a, 0, a.length / 2);
            int[] right = Arrays.copyOfRange(a, a.length / 2, a.length);

            if (threadCount <= 1) {

                parallelMergeSort(left, 1);
                parallelMergeSort(right, 1);

            } else {

                Thread lThread = new SorterThread(left, threadCount / 2);
                lThread.start();

                parallelMergeSort(right, threadCount / 2);

                try {
                    lThread.join();
                } catch (InterruptedException e) {
                    LOGGER.error(e.toString());
                }
            }

            merge(left, right, a);

        }
    }

    /**
     * Combines the contents of sorted left/right arrays into output array a.
     *
     * @param left  left part of array
     * @param right right part of array
     * @param a     resultative array
     */
    public static void merge(int[] left, int[] right, int[] a) {

        int i1 = 0;
        int i2 = 0;

        for (int i = 0; i < a.length; i++) {
            if (i2 >= right.length || (i1 < left.length && left[i1] < right[i2])) {
                a[i] = left[i1];
                i1++;
            } else {
                a[i] = right[i2];
                i2++;
            }
        }

    }

    /**
     * Entry point, used for testing.
     *
     * @param args
     */
    public static void main(String[] args) {

        final int arrayLength = 10000000;
        final int sortThreadsCount = 8;

        int[] a = Utils.createRandomArray(arrayLength);
        ParallelMergeSort parallelMergeSort = new ParallelMergeSort();

        LOGGER.info("Initial array: " + Arrays.toString(a));

        parallelMergeSort.parallelMergeSort(a, sortThreadsCount);

        if (!parallelMergeSort.isSorted(a)) {
            throw new Error("not sorted afterward: " + Arrays.toString(a));
        }

        LOGGER.info("Sorted array: " + Arrays.toString(a));
    }

    /**
     * Returns true if the given array is in sorted ascending order.
     */
    public boolean isSorted(int[] a) {

        for (int i = 0; i < a.length - 1; i++) {
            if (a[i] > a[i + 1]) {
                return false;
            }
        }
        return true;
    }

    /**
     * A SorterThread represents a task that can be run in a thread
     * and performs a merge sort on a given array.
     */
    public static class SorterThread extends Thread {

        private final int[] a;
        private int threadCount;

        /**
         * Common contructor.
         *
         * @param a           array to sort
         * @param threadCount thread available for sort
         */
        public SorterThread(int[] a, int threadCount) {
            this.a = a;
            this.threadCount = threadCount;
        }

        @Override
        public void run() {
            ParallelMergeSort.parallelMergeSort(a, threadCount);
        }
    }
}